package org.example.algorithm.sliding;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;

/**
 * !!! 该解法当words.length比较大时会超时
 */
public class FindSubstringSolution {

    public List<Integer> findSubstring(String s, String[] words) {
        List<Integer> list = new ArrayList<>();
        if (words.length == 0) {
            return list;
        }
        HashSet<String> set = buildStringSet(words);
        int len = words.length * words[0].length();
        for (int i=0;i<s.length()-len+1;i++) {
            String subString = s.substring(i, i+len);
            if (set.contains(subString)) {
                list.add(i);
            }
        }
        return list;
    }

    private HashSet<String> buildStringSet(String[] words) {
        HashSet<String> set = new HashSet<>();
        StringBuilder sb = new StringBuilder();
        HashSet<Integer> used = new HashSet<>();
        int totalCount = 0;
        doBuild(set, words, 0, sb, totalCount, used);
        return set;
    }

    private void doBuild(HashSet<String> set, String[] words, int index, StringBuilder sb, int totalCount, HashSet<Integer> used) {
        if (index == words.length) {
            set.add(sb.toString());
        } else {
            for (int i=0;i<words.length;i++) {
                //!used.contains(i-1)很关键，代表i-1处的值在这个for循环使用过
                if (i>=1 && words[i].equals(words[i-1]) && !used.contains(i-1)) {
                    continue;
                }
                if (used.contains(i)) {
                    continue;
                }
                int from = totalCount;
                sb.append(words[i]);
                totalCount += words[i].length();
                used.add(i);
                doBuild(set, words, index+1, sb, totalCount, used);
                sb.delete(from, totalCount);
                totalCount -= words[i].length();
                used.remove(i);
            }
        }

    }


    public static void main(String[] args) {
        String s = "bcabbcaabbccacacbabccacaababcbb";
        String[] words = {"a","a"};
        FindSubstringSolution solution = new FindSubstringSolution();
        List<Integer> list = solution.findSubstring(s, words);
        System.out.println(list);
    }
}
